#include "hash_table/anagram.h"

#include <algorithm>
#include <unordered_map>
#include <vector>

bool isAnagramLoop(const std::string& a, const std::string& b)
{
    if (a.size() != b.size() || a.empty())
        return false;

    std::string copy = b;
    for (const auto& c : a)
    {
        bool found = false;
        for (auto it = copy.begin(); it != copy.end(); it++)
        {
            if (*it == c)
            {
                copy.erase(it);
                found = true;
                break;
            }
        }
        if (!found)
        {
            return false;
        }
    }

    return true;
}

void anagramGroup(const std::vector<std::string>& arr,
                  std::vector<std::vector<std::string>>& groups)
{
    groups.clear();

    if (arr.empty())
        return;

    std::vector<bool> used(arr.size(), false);
    for (int i = 0; i < arr.size(); i++)
    {
        if (used[i])
            continue;
        std::vector<std::string> tmp;

        tmp.emplace_back(arr[i]);
        used[i] = true;

        for (int j = i + 1; j < arr.size(); j++)
        {
            if (isAnagramLoop(arr[i], arr[j]))
            {
                tmp.emplace_back(arr[j]);
                used[j] = true;
            }
        }

        groups.emplace_back(tmp);
    }
}

void anagramGroupByHashTable(const std::vector<std::string>& arr,
                             std::vector<std::vector<std::string>>& groups)
{
    groups.clear();

    if (arr.empty())
        return;

    std::unordered_map<std::string, std::vector<std::string>> table;
    std::vector<bool> used(arr.size(), false);

    for (int i = 0; i < arr.size(); i++)
    {
        if (used[i])
        {
            continue;
        }

        used[i] = true;
        std::string key = arr[i];
        std::sort(key.begin(), key.end());

        table[key].emplace_back(arr[i]);
    }

    groups.reserve(table.size());
    for (auto& pair : table)
    {
        groups.emplace_back(std::move(pair.second));
    }
}